package com.longge;

import java.util.Arrays;

/**
 * @program: my-code
 * @description: 堆排序
 * @author: longge
 * @create: 2021-04-05 16:42
 */
public class HeapMinSort {

    private void buildMinHeap(int[] arr, int n, int root) {
        int min = root;
        int l = 2 * root + 1;
        int r = 2 * root + 2;
        int temp;
        if (l <= n && arr[l] < arr[min]) {
            min = l;
        }
        if (r <= n && arr[r] < arr[min] ) {
            min = r;
        }

        if (min != root) {
            temp = arr[root];
            arr[root] = arr[min];
            arr[min] = temp;
            buildMinHeap(arr, n, min);
        }
    }

    public int[] sort(int[] arr) {
        int length = arr.length, temp;
        for (int i = length / 2 - 1; i >= 0; i--) {
            buildMinHeap(arr, length - 1, i);
        }

        for (int i = length - 1; i > 0; i--) {
            temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            buildMinHeap(arr, i - 1, 0);
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] sort = new HeapMinSort().sort(new int[]{6, 5, 4, 3, 2, 1, 1, 1, 1, 1, 5, 8, 2, 2, 3, 6, 8, 7, 9, 8, 7, 2, 5, 6, 4, 7});
        Arrays.stream(sort).forEach(System.out::print);
    }
}
